\section{Distributed algorithms for positive diffusions}
%\section{Diffusion time in dynamic networks}
\label{sec:diffusiontime}
Designing efficient distributed algorithms for positive diffusions is
crucial for the success of P2P, wireless, and sensor networked
systems. Indeed, a lot of research work has been devoted to this
problem
\cite{karp+ssv:rumor,feige+pru:broadcast,pittel:rumor,boyd+gps:gossip,elsasser+s:broadcast,kempe+k:gossip,ganesh+topology05,wang03,borgs+antidote10,liggett99}.
A major limitation in this line of work, however, is they only
consider diffusion processes defined on static networks. Only
recently, has there been some work on diffusion over dynamic
adversarial networks \cite{avin+kl:dynamic,kuhn+lo:dynamic}.

In our proposed research, we focus on dynamically changing
networks. We consider the following two types of dynamics. First, in
Section \ref{sec:diffusiontime-resource}, we look at the {\em resource
  discovery} problem, where the underlying dynamic network is changed
by the diffusion process itself. Second, in Section
\ref{sec:diffusiontime-adversary}, we look at the {\em token
  dissemination} problem, where the underlying dynamic network is
controlled by an adversary.

\subsection{Resource discovery}
\label{sec:diffusiontime-resource}
When a node joins a P2P system, it first discovers all the other
available nodes on the network. Such a problem is referred as resource
discovery problem. We model the P2P system by a graph. Each node
represents a resource (or a computer) in the network. If node $u$
knows node $v$, we assume that $u$ can communicate with $v$, and hence
there is an edge between $u$ and $v$. For example, if $u$ knows $v$'s
IP address, $u$ can send packages to $v$. Thus, as a node discovers
more and more other nodes, the graph changes dynamically. Such dynamic
is induced by the diffusion process itself.

We designed two distributed algorithms for resource discovery problem,
which are very easy to implement and deploy. The first algorithm is
the following: in each round, every node in the graph chooses two of
its neighbors randomly and ``introduces'' them to each other. This
algorithm can be analyzed by the follow {\em triangulation process}.

\smallskip
\BfPara{Triangulation process} Given a connected graph $G=(V,E)$, in
each round, for all $v\in V$, vertex $v$ picks 2 random neighbors $u$
and $w$, add an edge $(u,w)$ to graph $G$. The question is how many
rounds this process needs to take in order to make $G$ a complete
graph $K_n$.

\smallskip
The second algorithm is, in each round, every node in the graph choose
a random neighbor, and ask this neighbor to tell him a random node
that he knows. This algorithm can be analyzed by the following {\em
  2-hop random walk process}.

\smallskip
\BfPara{2-hop random walk process} Given a connected graph $G=(V,E)$,
in each round, for all $v\in V$, vertex $v$ takes a 2-hop random walk
and reaches vertex $u$. We add an edge $(v,u)$ to graph $G$. The
question is how many rounds this process needs to take in order to
make $G$ a complete graph $K_n$.

\subsubsection{Our results}
We have done a comprehensive simulations for both triangulation
process and 2-hop random walk process, over different families of
graphs. We observe that both processes complete quickly, in nearly
linear time. Thus, we conjecture that this is true across all families
of graphs. We will focus on proving this conjecture in future
research.

\subsubsection{Proposed research}
We plan to address the following open questions. We mainly focus on
proving rigorously what we observed in the simulation.

\begin{enumerate}
\item We conjecture that the completion time for the triangulation
  process and 2-hop random walk process is $O(n\log n)$ in undirected
  graphs. We will work on resolving this conjecture.
\item We conjecture that the completion time for the 2-hop random walk
  process in directed graphs is $O(n^2)$. We also conjecture that it
  is lower bounded by $\Omega(n^2)$. We will work on resolving these
  conjectures. 
\junk{
\item We have shown the completion time for both triangulation process
  and 2-hop random walk process is $O(n\log^2 n)$ in undirected
  graphs. It would be nice to improve this bound to $O(n\log n)$,
  which we conjecture to be the tight bound for both processes.
}
\junk{
\item The $O(n\log^2 n)$ bound proofs of 2 processes are similar yet
  different. Can we unify these 2 proofs?
}
\end{enumerate}

\subsection{Token dissemination}
%\subsection{Diffusions in adversarial networks}
\label{sec:diffusiontime-adversary}
Inspired by \cite{avin+kl:dynamic,kuhn+lo:dynamic}, we study the token
dissemination problem in adversarial networks. The adversary model is
important for many applications in wireless and P2P networks. Such
networks are highly dynamic, as nodes join, leave, and move around,
and as links appear and disappear. Such dynamic changes are not
under the control of users in the network.

\subsubsection{Definition}
\label{sec:diffusiontime-adversary-definition}
Let $V$ be the set of users in the contact/communication network, and
let $\abs{V} = n$. There are $k$ different pieces of information
assigned to a set of users, which we will refer as {\em tokens}. Each
user can hold different tokens. The goal is to diffuse all $k$ tokens
to all the users on the network. This information diffusion problem is
often refereed to as the $k$-token dissemination problem.

We consider synchronous communication in this model. The diffusion
process is divided into rounds. At the beginning of each round, the
{\em adversary} constructs the edges/links in the
contact/communication network. Namely, he decides which users can talk
to whom directly. Then, every user is allowed to exchange 1 token (or
constant number of tokens) with each of its neighbors in the contact
network. In our model, we assume the message size to be $\Theta(\log
n)$. Observe that, if the adversary is allowed to make the contact
network disconnected, then diffusing all $k$ tokens to all users is
impossible to complete. Therefore, we enforce the {\em connectivity}
constraint on the adversary. This means the adversary can arrange
edges whichever way he wants, but he has to make sure the contact
network is connected in each round.

\subsubsection{Our results}
Based on the model stated in Section
\ref{sec:diffusiontime-adversary-definition}, we proposed 2
distributed algorithms. One is {\sc PriorityForward}, shown in
Algorithm \ref{alg:pforward}. The other is {\sc RandomForward}, shown
in Algorithm \ref{alg:rforward}. We have shown the running time lower
bound for {\sc PriorityForward} is $\Omega(kn)$.

\algsetup{indent=2em}
\newcommand{\pforward}{\ensuremath{\mbox{\sc PriorityForward}}}
\begin{algorithm}[ht!]
\caption{$\pforward\rb{G}$}\label{alg:pforward}
\begin{algorithmic}[1]

  \REQUIRE Dynamic network $G=(V,E)$.
  \ENSURE Nodes receive all $k$ tokens.
  
  \medskip
  
  %\FORALL{$v$ such that $v\in V$}
  Each node $v$ executes the following procedure:
  \FORALL{$u$ such that $u$ is $v$'s neighbor in $G$}
  \STATE $v$ sends $u$ a token with lowest possible priority such that $u$ doesn't have this token yet.
  \ENDFOR

  %\IF{$v$ has all $k$ tokens}
  %\PRINT All $k$ tokens
  %\ENDIF
  %\ENDFOR
\end{algorithmic}
\end{algorithm}

\newcommand{\rforward}{\ensuremath{\mbox{\sc RandomForward}}}
\begin{algorithm}[ht!]
\caption{$\rforward\rb{G}$}\label{alg:rforward}
\begin{algorithmic}[1]

  \REQUIRE Dynamic network $G=(V,E)$.
  \ENSURE Nodes receive all $k$ tokens.
  
  \medskip
  
  %\FORALL{$v$ such that $v\in V$}
  Each node $v$ executes the following procedure:
  \FORALL{$u$ such that $u$ is $v$'s neighbor in $G$}
  \STATE $v$ sends $u$ a token randomly chosen from the tokens that $v$ has and $u$ doesn't have yet. \label{alg:rforward-diff}
  \ENDFOR

  %\IF{$v$ has all $k$ tokens}
  %\PRINT All $k$ tokens
  %\ENDIF
  %\ENDFOR
\end{algorithmic}
\end{algorithm}


\subsubsection{Proposed research}
We propose the following research problems in the adversarial network domain.

\begin{enumerate}
\item We conjecture that {\sc RandomForward} algorithm completes in
  $O(n\log k)$ time. We will work on resolving the conjecture.
\item In {\sc RandomForward} algorithm line \ref{alg:rforward-diff},
  we didn't state the time complexity for $v$ to choose a token which
  $u$ doesn't have at random. This problem can be formulated as
  follows. Nodes A and B both have an $n$-bit vector. A doesn't know
  the values of B's bit vector, and vice versa. Each time one can send
  the other a message of size $O(\log n)$, to query the values of its
  bit vector. How many messages have to be exchanged for A to identify
  a random bit position among all positions that are set in B's vector
  but not in A's vector.
\junk{
\item Consider different adversarial models, and devise efficient
  distributed algorithms for them.
}
\end{enumerate}
